#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <list>
using namespace std;

// 删除字符串中所有的相邻重复项
class Solution {
public:
    string removeDuplicates(string s) {
        string ret;
        for (auto ch : s)
        {
            if (ret.size() && ret.back() == ch)
            {
                ret.pop_back();
            }
            else
                ret += ch;
        }
        return ret;
    }
};

// 比较含退格的字符串
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string ret1, ret2;
        for (auto e : s)
        {
            if (ret1.size() && e == '#') ret1.pop_back();
            else if (e != '#')
                ret1 += e; 
        }
        for (auto e : t)
        {
            if (ret2.size() && e == '#') ret2.pop_back();
            else if (e != '#') ret2 += e;
        }
        return ret1 == ret2;
    }
};

// 基本计算器II
class Solution {
public:
    int calculate(string s) {
        vector<int> st;
        char op = '+';
        int i = 0, n = s.size();
        while (i < n)
        {
            if (s[i] == ' ') i++;
            else if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');
                if (op == '+') st.push_back(tmp);// 看当前字符前一个运算符是什么
                else if (op == '-') st.push_back(-tmp);
                else if (op == '*') st.back() *= tmp;
                else if (op == '/') st.back() /= tmp;
            }
            else op = s[i++];
        }
        int ret = 0;
        for (int e : st) 
            ret += e;
        return ret;
    }
};

// 字符串解码
class Solution {
public:
    string decodeString(string s) {
        stack<string> st1;
        st1.push("");
        stack<int> st2;
        int i = 0, n = s.size();
        while (i < n)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp*10 + (s[i++] - '0');
                st2.push(tmp);
            }
            else if (s[i] == '[')
            {
                i++;
                string str;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                    str += s[i++];
                st1.push(str);
            }
            else if (s[i] == ']')
            {
                i++;
                int n = st2.top();
                st2.pop();
                string str = st1.top();
                st1.pop();
                while (n--)
                {
                    st1.top() += str;
                }
            }
            else 
            {
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                    st1.top() += s[i++];
            }
        }
        return st1.top();
    }
};

// 验证栈序列
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int i = 0, n = popped.size();
        for (int e : pushed) {
            if (i < n && e == popped[i]) {
                i++;
                while (i < n && st.size() && st.top() == popped[i]) {
                    i++;
                    st.pop();
                }
            } 
            else
                st.push(e);
        }
        return st.empty();
    }
};

